DAG & Lineage

Apache Spark achieves its massive performance and incredible fault tolerance by completely changing how data replication is handled. Instead of physically replicating large chunks of data across multiple servers (like Hadoop HDFS's costly 3x replication), Spark uses a logical concept: The Directed Acyclic Graph (DAG) and the Lineage Graph.

What is a DAG?

A DAG (Directed Acyclic Graph) is a sequence of computation stages that Spark plans to execute on your data.

• Directed: The computations flow in a specific direction (from source data to final action output).
• Acyclic: There are no loops or circular loops in the execution path.
• Logical Plan: As you apply transformations to a DataFrame, Spark's DAG Scheduler logs them as a step-by-step blueprint of operations, rather than executing them.

What is a Lineage Graph?

The Lineage Graph (or Dependency Graph) is the detailed history of how a specific partition in a child RDD/DataFrame was derived from its parent partitions.

[Raw File Partition 1]  [Mapped Partition 1]  [Filtered Partition 1]  [Final Output]
                                   (If lost, Spark recomputes only this step!)

High Fault Tolerance Without Data Copying

In a traditional database or data lake, if an active server holding partition data crashes, the system must read the lost data from a replicated server. In Spark:

1. If an executor worker node crashes and loses its partition data in RAM, Spark does not panic.
2. It looks at the Lineage Graph of that specific partition.
3. Spark schedules a new task on another executor node to run the exact same sequence of transformations from the raw source file for only that single lost partition!
4. This dynamic, on-the-fly recomputation completely eliminates the network and disk cost of replicating data during normal execution runs!

Visualizing Lineage in PySpark

To inspect the underlying partition lineage graph of a dataset, you can access the RDD API from a DataFrame and call .toDebugString().

from pyspark.sql import SparkSession
from pyspark.sql.functions import col

# 1. Setup Spark
spark = SparkSession.builder \
    .appName("DAG and Lineage") \
    .master("local[*]") \
    .getOrCreate()

# 2. Raw Ingestion
raw_df = spark.read.format("csv") \
                   .option("header", "true") \
                   .load("dataset.csv")

# 3. Apply Transformations
transformed_df = raw_df.filter(col("price") > 100) \
                       .select("product_name", "price") \
                       .distinct() # Triggers wide dependency (shuffle)

# 4. View the underlying Lineage Graph of partitions
# .rdd retrieves the underlying RDD representation
lineage_string = transformed_df.rdd.toDebugString().decode("utf-8")
print("Lineage Graph Output:
", lineage_string)

Understanding the lineage output:

The .toDebugString() output will show nested levels of parentheses:

• Indented blocks represent different Stages separated by shuffles.
• Narrow transformations (like Map and Filter) appear inside the same block because they execute within the same stage.
• Wide transformations (like distinct/shuffles) start a new parent block, showing the lineage's partition count.